COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input acphdr % Section 4.1
C00003 00003	%folio 234 galley 1 (C) Addison-Wesley 1978	*
C00019 00004	%folio 237 galley 2 (C) Addison-Wesley 1978	*
C00037 00005	%folio 241 galley 3 (C) Addison-Wesley 1978	*
C00057 00006	%folio 245 galley 4 (C) Addison-Wesley 1978	*
C00071 00007	%folio 249 galley 5 (C) Addison-Wesley 1978	*
C00088 00008	%folio 254 galley 6 (C) Addison-Wesley 1978	*
C00107 00009	%folio 259 galley 7a (C) Addison-Wesley 1978	*
C00112 00010	\vfill\eject
C00113 ENDMK
C⊗;
\input acphdr % Section 4.1
\open0=v241.inx
\chpar19←1 % this will prepare a ".JST" file containing justification statistics
\runninglefthead{ARITHMETIC} % chapter title
\titlepage\setcount00
\null
\vfill
\tenpoint
\ctrline{SECTION 4.1 of THE ART OF COMPUTER PROGRAMMING}
\ctrline{$\copyright$ 1980 Addison--Wesley Publishing Company, Inc.}
\vfill
\runningrighthead{ARITHMETIC}
\section{4}
\eject
\setcount0 178
%folio 234 galley 1 (C) Addison-Wesley 1978	*
\titlepage\corners
\hbox{\def\\{\hskip 1pt}\:=C\\H\\A\\P\\T\\E\\R\hskip 10pt F\\O\\U\\R}
\vskip 1 cm plus 30 pt minus 10 pt
\rjustline{\:; \β{ARITHMETIC}}
\vskip .5 cm plus 1 pc minus 5 pt
\quoteformat{Seeing there is nothing (right well beloved Students in
the Mathematickes)\cr
that is so troublesome to Mathematicall practise, nor that doth more molest\cr
and hinder Calculators, then the Multiplications, Divisions, square and\cr
cubical Extractions of great numbers, which besides the tedious\cr
expence of time are for the most part subject to many slippery errors.\cr
I began therefore to consider in my minde, by what certaine and\cr
ready Art I might remove those hindrances.\cr}
\author{JOHN \α{NAPIER} (1614)}
\quoteformat{i do hate sums. There is no greater mistake than to call
arithmetic an exact\cr
science. There are . . . hidden laws of number which it requires a mind\cr
like mine to perceive. For instance, if you add a sum from the bottom up,\cr
and then again from the top down, the result is always different.\cr}
\author{MRS. \α{LA TOUCHE} (19th century)}
\quoteformat{I cannot conceive that anybody will require multiplications at
the rate\cr
of 40,000, or even 4,000 per hour; such a revolutionary change as the\cr
octonary scale should not be imposed upon mankind in general\cr
for the sake of a few individuals.\cr}
\author{F. H. \α{WALES} (1936)}
\quoteformat{Most numerical analysts have no interest in arithmetic.\cr}
\author{B. \α{PARLETT} (1979)}
\vskip 1 cm plus 1 pc minus 5 pt
\tenpoint\noindent T{\:mHE} {\:mCHIEF} {\:mPURPOSE} of this chapter is to make
a careful study of the four basic processes of arithmetic: addition,
subtraction, multiplication, and division. Many people regard
arithmetic as a trivial thing that children learn and computers
do, but we will see that arithmetic is a fascinating topic with
many interesting facets. It is important to make a thorough
study of efficient methods for calculating with numbers, since
arithmetic underlies so many computer applications.

Arithmetic is, in fact, a lively subject that has played an
important part in the history of the world, and it still is
undergoing rapid development. In this chapter, we shall analyze
algorithms for doing arithmetic operations on many types of
quantities, such as ``floating point'' numbers, extremely large
numbers, fractions (rational numbers), polynomials, and power
series; and we will also discuss related topics such as radix
conversion, factoring of numbers, and the evaluation of polynomials.

\runningrighthead{POSITIONAL NUMBER SYSTEMS} \section{4.1}
\eject
\sectionbegin{4.1. \β{POSITIONAL NUMBER SYSTEMS}}
T{\:mHE} {\:mWAY} {\:mWE} {\:mDO} {\:mARITHMETIC} is intimately related
to the way we represent the numbers we deal with, so it is appropriate
to begin our study of the subject with a discussion of the principal
\inxf{representation of numbers}
means for representing numbers.

Positional notation using base $b$ (or {\sl
radix} $b$) is defined by the rule
\inx{Radix: base of positional notation}
$$\eqalignno{⊗(\ldotsm a↓3a↓2a↓1a↓0.a↓{-1}a↓{-2}\ldotsm)↓b\cr
\noalign{\vskip 3pt}
⊗\qquad = \cdots + a↓3b↑3 + a↓2b↑2 + a↓1b↑1 + a↓0 + a↓{-1}b↑{-1}
+ a↓{-2}b↑{-2} + \cdotss;⊗(1)\cr}$$
for example, $(520.3)↓6 = 5 \cdot 6↑2 + 2 \cdot
6↑1 + 0 + 3 \cdot 6↑{-1} = 192{1\over 2}$. Our conventional decimal
number system is, of course, the special case when $b$ is ten,
and when the $a$'s are chosen from the ``\α{decimal digits}'' 0,
1, 2, 3, 4, 5, 6, 7, 8, 9; in this case the subscript $b$ in
(1) may be omitted.

The simplest generalizations of the decimal number
system are obtained when we take $b$ to be an integer greater
than 1 and when we require the $a$'s to be integers in the range
$0 ≤ a↓k < b$. This gives us the standard \α{binary} $(b = 2)$,
\α{ternary} $(b = 3)$, \α{quaternary} $(b = 4)$, \α{quinary} $(b = 5)$, $\ldots$
number systems. In general, we could take $b$ to be any nonzero
number, and we could choose the $a$'s from any specified set
of numbers; this leads to some interesting situations, as we
shall see.

The dot that appears between $a↓0$ and $a↓{-1}$ in (1) is called
the {\sl \α{radix point}.} (When $b = 10$, it is also called the
decimal point, and when $b = 2$, it is sometimes called the
binary point, etc.) Continental Europeans often use a comma instead of a
dot to denote the radix point; Englishmen often use a raised
dot.

The $a$'s in (1) are called the {\sl \α{digits}} of the representation.
A digit $a↓k$ for large $k$ is often said to be ``more significant''
\inx{leading digit}
\inx{trailing digit}
\inx{most significant digit}
\inx{least significant digit}
\inx{significant digit}
than the digits $a↓k$ for small $k$; accordingly, the leftmost
or ``leading'' digit is referred to as the {\sl most significant
digit\/} and the rightmost or ``trailing'' digit is
referred to as the {\sl least significant digit}.
In the standard binary system the \α{binary digits} are
often called {\sl \α{bits}}; in the standard hexadecimal system
(radix sixteen) the \α{hexadecimal digits} zero through fifteen
are usually denoted by
$$\def\\{{\:a, }}\hbox{\tt 0\\1\\2\\3\\4\\5\\6\\7\\8\\9\\A\\B\\C\\D\\E\\F\rm.}$$

The historical development of number representations
is a fascinating story, since it parallels the development of
civilization itself. We would be going far afield if we were
to examine this history in minute detail, but it will be instructive
to look at its main features here.

The earliest forms of number representations, still found in
\inx{number systems, primitive}
primitive cultures, are generally based on groups of fingers,
piles of stones, etc., usually with special conventions about
replacing a larger pile or group of, say, five or ten objects
by one object of a special kind or in a special place. Such
systems lead naturally to the earliest ways of representing
numbers in written form, as in the systems of
Babylonian, Egyptian,
Greek, Chinese, and \α{Roman numerals}; but such notations are comparatively
inconvenient for performing arithmetic operations except in
the simplest cases.

\penalty-500 % please break here (April 1980)
During the twentieth century, historians of mathematics
have made extensive studies of early cuneiform tablets found
by archeologists in the Middle East. These studies show that
the Babylonian people actually had two distinct systems of number
representation: Numbers used in everyday business transactions
were written in a notation based on grouping by tens, hundreds,
etc.; this notation was inherited from earlier Mesopotamian
civilizations, and large numbers were seldom required. When
more difficult mathematical problems were considered, however,
Babylonian mathematicians made extensive use of a \α{sexagesimal}
(radix sixty) positional notation that was highly developed
at least as early as 1750 {\:mB.C.}
This notation was unique in that it was actually a {\sl \α{floating point}\/}
form of representation with exponents omitted; the proper scale
factor or power of sixty was to be supplied by the context,
so that, for example, the numbers 2, 120, 7200, and ${1\over 30}$
were all written in an identical manner. The notation was
especially convenient for multiplication and division, using
auxiliary tables, since radix-point alignment had no effect
on the answer. As examples of this Babylonian notation, consider
the following excerpts from early tables: The square of 30 is
15 (which may also be read, ``The square of ${1\over 2}$ is
${1\over 4}$''); the reciprocal of $81 = (1\,\,21)↓{60}$ is $(44\,\,
26\,\,40)↓{60}$; and the square of the latter is $(32\,\,55\,\,18\,\,31\,\,6\,\,
40)↓{60}$. The Babylonians had a sym\-bol for zero, but because
of their ``floating point'' philosophy, it was used only within
numbers, not at the right end to denote a scale factor. For
the interesting story of early \α{Babylonian mathematics}, see O.
\α{Neugebauer,} {\sl The Exact Sciences in Antiquity} (Princeton, N. J.:
Princeton University
Press, 1952), and B. L. \α{van der Waerden}, {\sl Science Awakening},
tr.\ by A. \α{Dresden} (Groningen: P. Noordhoff, 1954); see also
D. E. \α{Knuth,} {\sl CACM} {\bf 15} (1972), 671--677; {\bf19} (1976),↔108.

Fixed point positional notation was apparently first conceived
by the \α{Maya Indians} in central America 2000 years ago; their
\inx{vigesimal number system}
radix-20 system was highly developed, especially in connection
with astronomical records and calendar dates. But the Spanish
conquerors destroyed nearly all of the Maya books on history
and science, so we have comparatively little knowledge about
how sophisticated the native Americans had become
at arithmetic; special-purpose multiplication tables have
been found, but no examples of division are known [cf.\ J. Eric
S. \α{Thompson,} {\sl Con\-tri\-bu\-tions to Amer.\ Anthropology and History
\bf 7} (Carnegie Inst.\ of Washington, 1942), \hbox{37--62}].

Several centuries before Christ, the Greek people employed an
\inxf{Greek mathematics}
early form of the \α{abacus} to do their arithmetical calculations,
using sand and/or pebbles on a board that had rows or columns
corresponding in a natural way to our decimal system. It is
perhaps surprising to us that the same positional notation was
never adapted to written forms of numbers, since we are so accustomed
to reckoning with the decimal system using pencil and paper;
but the greater ease of calculating by abacus (since handwriting
was not a common skill, and since abacus calculation makes
it unnecessary to memorize addition and multiplication tables)
probably made the Greeks feel it would be silly even to suggest
that computing could be done better on ``scratch paper.'' At the
same time Greek astronomers did make use of a sexagesimal positional
notation for fractions, which they had learned from the Babylonians.
%folio 237 galley 2 (C) Addison-Wesley 1978	*
\def\\{{\:mA.D.}}
Our \β{decimal notation}, which differs from
the more ancient forms primarily because of its fixed radix
point, together with its symbol for zero to mark an empty position,
was developed first in India within the Hindu culture. The exact
\inx{Indian mathematics}
date when this notation first appeared is quite uncertain; about
600 \\\ seems to be a good
guess. \β{Hindu science} was rather highly developed at that time,
particularly in astronomy. The earliest known Hindu manuscripts
that show this notation have numbers written backwards (with
the most significant digit at the right), but soon it became
standard to put the most significant digit at the left.

About 750 \\, the Hindu
\inxf{Arabic mathematics}
\inxf{Persian mathematics}
principles of decimal arithmetic were brought to Persia, as
several important works were translated into Arabic; a picturesque
account of this development is given in a Hebrew document, which
has been translated into English in {\sl AMM \bf 15} (1918),
99--108. Not long after this, \α{al-Khow\A arizm\A\i}\
wrote his Arabic textbook on the subject.\xskip (As noted in Chapter↔1,
our word ``algorithm'' comes from al-Khow\A arizm\A\i's
name.)\xskip His book was translated into Latin and was a strong
influence on \α{Leonardo Pisano} (\α{Fibonacci}), whose book on arithmetic
(1202 \\) played a major
role in the spreading of Hindu-Arabic numerals into Europe.
It is interesting to note that the left-to-right order\-\ of writing
numbers was unchanged during these two transitions,
although Arabic is written
from right to left while Hindu and Latin scholars generally wrote from left
to right. A detailed account of the subsequent propagation of
decimal numeration and arithmetic into all parts of Europe during
the period from 1200 to 1600 \\\
has been given by David Eugene \α{Smith} in his {\sl History of Mathematics
\bf 1} (Boston: Ginn and Co., 1923), Chapters 6 and↔8.

\def\¬{\scriptscriptstyle}
Decimal notation was applied at first only to integer numbers,
not to fractions. Arabic astronomers, who required fractions
in their star charts and other tables, continued to use the
notation of \α{Ptolemy} (the famous Greek astronomer), a notation
based on \α{sexagesimal} fractions. This system still survives today,
in our trigonometric units of ``degrees, minutes, and seconds,''
and also in our units of time, as a remnant of the original
Babylonian sexagesimal notation. Early European mathematicians
also used sexagesimal fractions when dealing with noninteger
numbers; for example, Fibonacci gave the value
$$1\deg\;22↑\prime\;7↑{\prime\prime}\;42↑{\prime\prime\prime}\;
33↑{\¬I\!V}\;4↑{\¬V}\;40↑{\¬V\!\!I}$$
as an approximation to the root of the equation
$x↑3 + 2x↑2 + 10x = 20$.\xskip (The correct answer is $1\deg$ $22↑\prime$
$7↑{\prime\prime}$ $42↑{\prime\prime\prime}$ $33↑{\¬I\!V}$ $4↑{\¬V}$
$38↑{\¬V\!\!I}$ $30↑{\¬V\!\!I\!I}$ $50↑{\¬V\!\!I\!I\!I}$ $15↑{\¬I\!X}$
$43↑{\¬X}$ $\ldotss\,$.)

The use of decimal notation also for tenths, hundredths,
etc., in a similar way seems to be a comparatively minor change;
but, of course, it is hard to break with tradition, and sexagesimal
fractions have an advantage over \β{decimal fractions} in that numbers
such as ${1\over 3}$ can be expressed exactly, in a simple way.

\β{Chinese mathematicians}---who never used sexagesimals---were apparently the
first people to work with the equivalent of decimal fractions,
although their numeral system (lacking zero) was not originally
a positional number system in
the strict sense. Chinese units
of weights and measures were decimal, so that \α{Tsu Chhung-Chih}
(who died c.\ 500 \\) was
\inx{Pi}
able to express an approximation\eject % break here (April 1980)
to $π$ in the following form: $$\hbox{3 chang, 1 chhih,
4 tshun, 1 f\A en, 5 li, 9 hao, 2 miao, 7 hu.}$$ Here chang,
$\ldotss$, hu are units of length; 1 hu (the diameter of a silk
\inxf{weights and measures}
thread) equals 1/10 miao, etc. The use of such decimal-like
fractions was fairly widespread in China after about 1250 \\

The first known appearance of
decimal fractions in a true positional system occurs in a 10th-century
arithmetic text written in Damascus by an obscure mathematician
named \α{al-Uql\A\i dis\A\i}\ (``the Euclidean''). He
used the symbol $↑\prime$ for a decimal point, for example in connection with
a problem about compound interest, the computation of 135 times $(1.1)↑n$ for
$1≤n≤5$.\xskip[See A. S. \α{Saidan}, {\sl The Arithmetic of al-Uql\=\i dis\=\i}
(Dordrecht: D. Reidel, 1975), 110, 114, 343, 355, 481--485.]\xskip
But he did not develop the idea very fully, and his trick
was soon forgotten;
five centuries passed before decimal fractions
were reinvented by a Persian mathematician, \α{al-Kash\A\i},
who died c.\ 1436. Al-Kash\A\i\ was a highly skillful calculator,
who gave the value of $2π$ as follows, correct to 16 decimal
places:
$$\vbox{\hrule
\baselineskip0pt \lineskip0pt
\def\\{\vrule height 11.47222pt depth 4.52778pt} % good for 10 pt type on 16 pt base
\hbox to 28pc{\hbox to 4pc{\\\hfill integer\hfill\\}\hfill fractions\hfill\\}
\hrule
\hbox to 28pc{\hbox to 4pc{\\\hfill0\hfill\\\hfill6\hfill\\}\hfill2\hfill\\
\hfill8\hfill\\\hfill3\hfill\\\hfill1\hfill\\\hfill8\hfill\\\hfill5\hfill\\
\hfill3\hfill\\\hfill0\hfill\\\hfill7\hfill\\\hfill1\hfill\\\hfill7\hfill\\
\hfill9\hfill\\\hfill5\hfill\\\hfill8\hfill\\\hfill6\hfill\\\hfill5\hfill\\}
\hrule}$$
This was by far the best approximation to
$π$ known until Ludolph \α{van Ceulen} laboriously calculated 35
decimal places during the period 1596--1610.

The earliest known
example of decimal fractions in Europe occurs in a 15th-century
text where, for example, 153.5 is multiplied by 16.25 to get
2494.375; this was referred to as a ``Turkish method.'' In 1525,
Christof \α{Rudolff} of Germany discovered decimal fractions for
himself; but like al-Uql\A\i dis\A\i, his work seems to have had little
influence. Fran\c
cois \α{Vi\`ete} suggested the idea again in 1579. Finally,
an arithmetic text by Simon \α{Stevin} of Belgium, who independently
hit on the idea of decimal fractions in 1585, became popular.
Stevin's work, and the discovery of logarithms soon afterwards, made
decimal fractions commonplace in Europe during the 17th century.\xskip
[See D. E. \α{Smith,} {\sl History of Mathematics \bf 2} (Boston:
Ginn and Co., 1925), 228--247, and C. B. \α{Boyer,} {\sl History
of Mathematics} (New York: Wiley, 1968), for further remarks
and references.]

\yskip The \β{binary} system of notation has its own interesting history.
Many primitive tribes in existence today are known to use a
binary or ``pair'' system of counting (making groups of two
instead of five or ten), but they do not count in a true radix-2
system, since they do not treat powers of 2 in a special manner.
See {\sl The Diffusion of Counting Practices} by Abraham \α{Seidenberg},
{\sl Univ.\ Calif.\ Publ.\ in Math.\ \bf 3} (1960), 215--300, for interesting
\inx{number systems, primitive}
details about primitive number systems. Another ``primitive''
example of an essentially binary system is the conventional
musical notation for expressing rhythms and durations of time.

Nondecimal number systems were discussed in Europe during the
seventeenth century. For many years astronomers had occasionally
used \α{sexagesimal} arithmetic both for the integer and the fractional
parts of numbers, primarily when performing multiplication [see
John \α{Wallis,} {\sl Treatise of Algebra} (Oxford,\eject %break here (April 80)
1685), 18--22,
30]. The fact that {\sl any} integer greater than 1 could serve as
radix was apparently first stated in print by Blaise \α{Pascal}
in {\sl De numeris multiplicibus}, which was written about 1658
[see Pascal's {\sl \OE uvres Compl\`etes} (Paris: \'Editions
de Seuil, 1963), 84--89]. Pascal wrote, ``Denaria enim ex institute
hominum, non ex necessitate natur\ae\ ut vulgus arbitratur, et
sane satis inepte, posita est''; i.e., ``The \α{decimal system}
has been established, somewhat foolishly to be sure, according
to man's custom, not from a natural necessity as most people
would think.'' He stated that the \α{duodecimal} (radix twelve)
system would be a welcome change, and he gave a rule for testing
a duodecimal number for divisibility by nine. Erhard \α{Weigel}
tried to drum up enthusiasm
for the quaternary (radix four) system in a series of publications
beginning in 1673. A detailed discussion of radix-twelve arithmetic
was given by Joshua \α{Jordaine,} {\sl Duodecimal Arithmetick} (London,
1687).

Although decimal notation was almost exclusively used for arithmetic
during that era, other systems of weights and measures were
rarely if ever based on multiples of 10, and many business transactions
required a good deal of skill in adding quantities such as pounds,
shillings, and pence. For centuries merchants had therefore
learned to compute sums and differences of quantities expressed
\inx{mixed-radix number systems}
in peculiar units of currency, weights, and measures; and this
was actually arithmetic in a nondecimal number system. The common
units of \α{liquid measure} in England, dating from the 13th century
or earlier, are particularly noteworthy:
$$\teqalign{\hbox{2 gills}⊗=\hbox{1 chopin}\cr
\hbox{2 chopins}⊗=\hbox{1 pint}\cr
\hbox{2 pints}⊗=\hbox{1 quart}\cr
\hbox{2 quarts}⊗=\hbox{1 pottle}\cr
\hbox{2 pottles}⊗=\hbox{1 gallon}\cr
\hbox{2 gallons}⊗=\hbox{1 peck}\cr
\hbox{2 pecks}⊗=\hbox{1 demibushel}\cr}\qquad\teqalign{
\hbox{2 demibushels}⊗=\hbox{1 bushel or firkin}\cr
\hbox{2 firkins}⊗=\hbox{1 kilderkin}\cr
\hbox{2 kilderkins}⊗=\hbox{1 barrel}\cr
\hbox{2 barrels}⊗=\hbox{1 hogshead}\cr
\hbox{2 hogsheads}⊗=\hbox{1 pipe}\cr
\hbox{2 pipes}⊗=\hbox{1 tun}\cr}$$
Quantities of liquid expressed in gallons, pottles, quarts,
pints, etc.\ were essentially written in binary notation. Perhaps
the true inventors of binary arithmetic were English wine merchants!

The first known appearance of pure binary notation was about 1605
in some unpublished manuscripts of Thomas \α{Harriot} (1560--1621).
Harriot was a creative man, who first became famous by coming to America
as a representative
of Sir Walter \α{Raleigh}. He invented (among other things) a notation
like that now used for ``less than'' and ``greater than'' relations;
but for some reason he chose not to publish many of his discoveries.
Excerpts from his notes on binary arithmetic have been reproduced
by John W. \α{Shirley,} {\sl Amer.\ J. Physics \bf 19} (1951), 452--454.
The first published discussion of the binary system was given
in a comparatively little-known work by a Spanish bishop, Juan
\α{Caramuel Lobkowitz}, {\sl Mathesis biceps \bf 1} (Campani\ae,
1670), 45--48; Caramuel discussed the representation of numbers
\inx{ternary}
\inx{quaternary}
\inx{quinary}
\inx{Septenary (radix 7) number system}
\inx{octal number system}
\inx{Nonary (radix 7) number system}
\inx{duodecimal}
\inx{sexagesimal}
in radices 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, and 60 at some length,
but gave no examples of arithmetic operations in nondecimal
systems (except for the trivial operation of adding unity).
%folio 241 galley 3 (C) Addison-Wesley 1978	*
Ultimately, an article by G. W. \β{Leibniz}
[{\sl Memoires de l'Academie Royale des Sciences} (Paris: 1703),
110--116], which illustrated binary addition, subtraction, multiplication,
and division, really brought binary notation into the limelight,
and this article is usually referred to as the birth of radix-2
arithmetic. Leibniz later referred to the binary system quite
frequently. He did
not recommend it for practical calculations, but he stressed
its importance in number-theoretical investigations, since patterns
in number sequences are often more apparent in binary notation
than they are in decimal; he also saw a mystical significance
in the fact that everything is expressible in terms of zero
and one. Leibniz's unpublished manuscripts show that he had been interested
in binary notation as early as 1679, when he referred to it as a ``bimal''
system (analogous to ``decimal'').

A careful study of Leibniz's early work with binary numbers has been made by
Hans J. \α{Zacher,} {\sl Die Hauptschriften zur Dyadik von G. W. Leibniz}
(Frankfurt am Main: Klostermann, 1973). Zacher points out that Leibniz was
familiar with John \α{Napier}'s so-called ``\α{local arithmetic},'' a way for
calculating with stones that amounts to using a radix-2 \α{abacus}.\xskip [Napier had
published the idea of local arithmetic as an appendix to his little book
{\sl Rhabdologia} in 1617; it may be called the world's first ``binary
computer,'' and it is surely the world's cheapest, although Napier felt that
it was more amusing than practical. See Martin \α{Gardner}'s discussion in
{\sl Scientific American \bf228} (April 1973), 106--111.]

It is interesting to note that the important concept of negative
powers to the right of the radix point was not yet well understood
at that time. Leibniz asked James \α{Bernoulli} to calculate $π$
\inx{Pi}
\inx{radix conversion}
in the binary system, and Bernoulli ``solved'' the problem by
taking a 35-digit approximation to $π$, multiplying it by $10↑{35}$,
and then expressing this integer in the binary system as his
answer. On a smaller scale this would be like saying that $π
\approx 3.14$, and $(314)↓{10} = (100111010)↓2$; hence $π$ in
binary is 100111010!\xskip [See Leibniz, {\sl Math.\ Schriften} (ed.\
Gehrhardt), {\bf 3} (Halle: 1855), 97; two of the 118 bits in
the answer are incorrect, due to computational errors.]\xskip The
motive for Bernoulli's calculation was apparently to see whether
any simple pattern could be observed in this representation
of $π$.

\α{Charles XII} of Sweden, whose talent for mathematics
perhaps exceeded that of all other kings in the history of the
\inxf{octal number system}
world, hit on the idea of radix-8 arithmetic about 1717. This
was probably his own invention, although he had met Leibniz
briefly in 1707. Charles felt that radix 8 or 64 would be more convenient
for calculation than the decimal system, and he considered introducing
octal arithmetic into Sweden; but he died in battle before decreeing
such a change.\xskip [See {\sl The Works of \α{Voltaire} \bf 21} (Paris:
E. R. DuMont, 1901), 49; E. \α{Swedenborg,} {\sl Gentleman's Magazine
\bf 24} (1754), 423--424.]

Octal notation was proposed also in colonial America before
1750, by the Rev.\ Hugh \α{Jones,} rector of a parish in Maryland
[cf.\ {\sl Gentleman's Magazine \bf 15} (1745), 377--379; H.
R. \α{Phalen,} {\sl AMM \bf 56} (1949), 461--465].

More than a century later, a prominent Swedish-American civil
engineer named John W. \β{Nystrom} decided to carry Charles XII's
plans a step further, by devising a complete system of numeration,
weights, and measures based on radix-16 arithmetic.
He wrote, ``I am not afraid, or do not hesitate, to advocate
a binary system of arithmetic and metrology. I know I have nature
on my side; if I do not succeed to impress upon you its utility
and great importance to mankind, it will reflect that much less
credit upon our generation, upon our scientific men and philosophers.''
Nystrom devised special means for pronouncing \β{hexadecimal} numbers;
e.g., $(\.{B0160})↓{16}$ was to be read ``vybong, bysanton.'' His
entire system was called the Tonal System, and it is described
in {\sl J. Franklin Inst.\ \bf 46} (1863), 263--275, 337--348, 402--407.
A similar system, but using radix 8, was worked out by Alfred
B. \α{Taylor} [{\sl Proc.\ Amer.\ Pharmaceutical Assoc.\ \bf 8} (1859),
115--216; {\sl Proc.\ Amer.\ Philosophical Soc.\ \bf 24} (1887), 296--366].
Increased use of the French (metric) system of weights and measures
prompted extensive debate about the merits of decimal arithmetic
during that era; indeed, octal arithmetic was even being proposed
in France [J. D. \α{Colenne,} {\sl Le syst\`eme octaval\/} (Paris: 1845);
Aim\'e \α{Mariage,} {\sl Num\'eration par huit}
(Paris: Le Nonnant, 1857)].

The binary system was well known as a curiosity ever since Leibniz's
time, and about 20 early references to it have been compiled
by R. C. \α{Archibald} [{\sl AMM \bf 25} (1918), 139--142]. It was
applied chiefly to the calculation of powers, as explained in
Section 4.6.3, and to the analysis of certain games and puzzles.
Giuseppe \α{Peano} [{\sl Atti della R. Accademia delle Scienze di Torino
\bf 34} (1898), 47--55] used binary notation as the basis of
a ``logical'' character set of 256 symbols. Joseph \α{Bowden} [{\sl
Special Topics in Theoretical Arithmetic} (Garden City: 1936),
49] gave his own system of nomenclature for hexadecimal numbers.

The book {\sl History of Binary and Other Nondecimal Numeration}
by Anton \α{Glaser} (privately printed, 1971) contains an informative
and nearly complete discussion of the development of binary
notation, including English translations of many of the works
cited above.

\yskip Much of the recent history of number systems is connected with
the development of calculating machines. Charles \α{Babbage}'s notebooks for
1838 show that he considered using nondecimal numbers in his \α{Analytical
Engine} [cf.\ M. V. \α{Wilkes,} {\sl Historia Math.\ \bf4} (1977), 421].
Increased interest in mechanical devices for arithmetic, especially
for multiplication,
led several people in the 1930s to consider
the binary system for this purpose. A particularly delightful
account of such activity appears in the article ``Binary Calculation''
by E. William \α{Phillips} [{\sl Journal of the Institute of Actuaries
\bf 67} (1936), 187--221] together with a record of the discussion
that followed a lecture he gave on the subject. Phillips began
by saying, ``The ultimate aim [of this paper] is to persuade
the whole civilized world to abandon decimal numeration and
to use octonal [i.e., radix 8] numeration in its place.''

Modern readers of Phillips's article will perhaps be surprised
to discover that a radix-8 number system was properly referred
to as ``octonary'' or ``octonal,'' according to all dictionaries
of the English language at that time, just as the radix-10 number
system is properly called either ``denary'' or ``decimal'';
the word ``octal'' did not appear in English language dictionaries
until 1961, and it apparently originated as a term for the ``base''
of a certain class of vacuum tubes. The word ``hexadecimal,''
which has crept into our language even more recently, is a mixture
of Greek and Latin stems; more proper terms would be ``senidenary''
or ``sedecimal'' or even ``sexadecimal,'' but the latter is
perhaps too risqu\'e for computer programmers.

The comment by Mr.\ \α{Wales} that is quoted at the beginning of
this chapter has been taken from the discussion printed with
Phillips's paper. Another man who attended the same lecture
objected to the octal system for business purposes: ``$5\%$ becomes
\def\\#1{{\baselineskip0pt \lineskip1pt \vbox{\hbox to 5pt{\hfill.\hfill}
\hbox{#1}}}} % puts dots over a digit
3.\\146\\3 per 64, which sounds rather horrible.''

Phillips got the inspiration for his proposals from an electronic
circuit that was capable of counting in binary [C. E. \α{Wynn-Williams},
Proc.\ Roy.\ Soc.\ London {\bf A136} (1932), 312--324]. Electromechanical
and electronic circuitry for general arithmetic operations was
developed during the late 1930s, notably by John V. \α{Atanasoff}
and George R. \α{Stibitz} in the U.S.A., L. \α{Couffignal} and R. \α{Valtat}
in France, Helmut \α{Schreyer} and Konrad \α{Zuse} in Germany. All of
these inventors used the binary system, although \α{Stibitz} later
developed excess-3 \α{binary-coded-decimal} notation. A fascinating
account of these early developments, including reprints and
translations of important contemporary documents, appears in
Brian \α{Randell}'s book {\sl The Origins of Digital Computers}
(Berlin: Springer, 1973).

The first American high-speed computers, built in the early
1940s, used decimal arithmetic. But in 1946, an important memorandum
by A. W. \α{Burks,} H. H. \α{Goldstine,} and J. \α{von Neumann}, in connection
with the design of the first stored-program computers, gave
detailed reasons for the decision to make a radical departure
from tradition and to use base-two notation [see John von Neumann,
{\sl Collected Works \bf 5}, 41--65]. Since then binary computers
have multiplied. After a dozen years of experience
with binary machines, a discussion of the relative advantages
and disadvantages of radix-2 notation was given by W. \α{Buchholz}
in his paper ``Fingers or Fists?'' [{\sl CACM \bf 2} (December
1959), 3--11].

The \α{\MIX}\ computer used in this book has been defined so that
it can be either binary or decimal. It is interesting to note
that nearly all \MIX\ programs can be expressed without knowing
whether binary or decimal notation is being used---even when
we are doing calculations involving \α{multiple-precision arithmetic}.
Thus we find that the choice of radix does not significantly
influence computer programming.\xskip (Noteworthy exceptions to this
statement, however, are the ``Boolean'' algorithms discussed
in Section 7.1; see also Algorithm 4.5.2B.)

\yskip There are several different methods for representing {\sl negative}
\inxf{negative numbers, representation of}
numbers in a computer, and this sometimes influences the way
arithmetic is done. In order to understand these other notations,
let us first consider \MIX\ as if it were a decimal computer;
then each word contains 10 digits and a sign, for example
$$-12345\ 67890.\eqno (2)$$
This is called the {\sl signed-magnitude} representation.
\inxf{signed-magnitude representation}
Such a representation agrees with common notational conventions,
so it is preferred by many programmers. A potential disadvantage
is that \α{minus zero} and plus zero can both be represented, while
they usually should mean the same number; this possibility requires
some care in practice, although it turns out to be useful at times.

Most mechanical calculators that do decimal arithmetic use another
system called {\sl ten's complement\/} notation. If we subtract 1
\inx{ten's complement notation}
from $00000\ 00000$, we get $99999\ 99999$ in this notation; in other
words, no explicit sign is attached to the number, and calculation
is done {\sl modulo} $10↑{10}$. The number $-12345\ 67890$ would
appear as
$$87654\ 32110\eqno (3)$$
in ten's \α{complement notation}. It is conventional
to regard any number whose leading digit is 5, 6, 7, 8, or 9
as a negative value in this notation, although with respect
to addition and subtraction there is no harm in regarding (3)
as the number $+87654\ 32110$ if it is convenient to do so. Note that there
is no problem of ``minus zero'' in such a system.

The major difference between signed magnitude and
ten's complement notations in practice is that shifting right
does not divide the magnitude by ten; for example, the number
$-11 = \ldotss 99989$, shifted right one, gives $\ldotss 99998
= -2$ (assuming that a shift to the right inserts ``9'' as the
leading digit when the number shifted is negative). In general,
$x$ shifted right one digit in ten's complement notation will
give $\lfloor x/10\rfloor $, whether $x$ is positive or negative.

A possible disadvantage of the ten's complement system is the
fact that it is not symmetric about zero; the largest negative
number representable in $p$ digits is $500\ldotsm0$, and it is not
the negative of any $p$-digit positive number. Thus it is possible
that changing $x$ to $-x$ will cause overflow.\xskip (See exercises 7 and↔31
for a discussion of radix-complement notation with {\sl infinite}
precision.)
%folio 245 galley 4 (C) Addison-Wesley 1978	*
Another notation that has been used since
the earliest days of high-speed computers is called {\sl nines'
\inx{nines' complement notation}
complement\/} representation. In this case the number $-12345\ 67890$
would appear as
$$87654\ 32109.\eqno (4)$$
Each digit of a negative number $(-x)$ is equal to
9 minus the corresponding digit of↔$x$. It is not difficult
to see that the nines' complement notation for a negative number
is always one less than the corresponding ten's complement notation.
Addition and subtraction are done modulo $10↑{10} - 1$, which
means that a carry off the left end is to be added at the right
end.\xskip (Cf.\ Section 3.2.1.1.)\xskip Again there is a potential problem
with minus zero, since $99999\ 99999$ and $00000\ 00000$ denote the
same value.

The ideas just explained for base-10 arithmetic apply in a similar
way to base-2 arithmetic, where we have {\sl signed magnitude},
{\sl \α{two's complement}}, and {\sl \α{ones' complement}} notations. The
\α{\MIX}\ computer, as used in the examples of this chapter, deals
only with signed-magnitude arithmetic; however, alternative procedures
for complement notations are discussed in the accompanying text
when it is important to do so.

Most computer manuals tell us that the machine's circuitry assumes
that the \α{radix point} is situated in a particular place within
each computer word. This advice should usually be disregarded.
It is better to learn the rules concerning where the radix point
will appear in the result of an instruction if we assume that
it lies in a certain place beforehand. For example, in the case
of \MIX\ we could regard our operands either as integers with
the radix point at the extreme right, or as fractions with the
radix point at the extreme left, or as some mixture of these
two extremes; the rules for the appearance of the radix point
in each result are straightforward.

\yskip It is easy to see that there is a simple relation between radix
$b$ and radix $b↑k$:
$$(\ldotsm a↓3a↓2a↓1a↓0.a↓{-1}a↓{-2}\ldotsm)↓b = (\ldotsm A↓3A↓2A↓1A↓0.A↓{-1}A↓{-2}
\ldotsm)↓{b↑k},\eqno (5)$$
where
$$A↓j = (a↓{kj+k-1} \ldotsm a↓{kj+1}a↓{kj})↓b;$$
see exercise↔8. Thus we have simple techniques
\inx{radix conversion}
for converting at sight between, say, binary and octal notation.

\yskip Many interesting variations on positional number systems are possible
besides the standard $b$-ary systems discussed so far. For example,
we might have numbers in base $(-10)$, so that
\inxf{negative radix}
$$\eqalign{⊗(\ldotsm a↓3a↓2a↓1a↓0.a↓{-1}a↓{-2}\ldotsm)↓{-10}\cr
\noalign{\vskip 3pt}
⊗\qquad= \cdots + a↓3(-10)↑3 + a↓2(-10)↑2 + a↓1(-10)↑1 +
a↓0 + \cdots\cr
\noalign{\vskip 3pt}
⊗\qquad\textstyle=\cdots-1000a↓3+100a↓2-10a↓1+a↓0-{1\over10}a↓{-1}
+{1\over100}a↓{-2}-\cdotss.\cr}$$
Here the individual digits satisfy $0 ≤ a↓k
≤ 9$ just as in the decimal system. The number $12345\ 67890$
appears in the ``\α{negadecimal}'' system as
$$(1\ 93755\ 73910)↓{-10},\eqno (6)$$
since the latter represents $10305070900 - 9070503010$.
It is interesting to note that the negative of this number,
$-12345\ 67890$, would be written
$$(28466\ 48290)↓{-10},\eqno (7)$$
and, in fact, {\sl every real number whether positive
or negative can be represented without a sign} in the $-10$ system.

Negative-base systems were first considered by Vittorio 
\α{Gr\"unwald} [{\sl Giornale di matematiche di Battaglini \bf 23}
(1885), 203--221, 367], who explained how to perform the four
arithmetic operations in such systems; Gr\"unwald also discussed root
extraction, divisibility tests, and \α{radix conversion}. However,
since his work was published in a rather obscure journal, it
seems to have had no effect on other research, and it was soon
forgotten. The next publication about negative-base systems\-\
was apparently by A. J. \α{Kempner} [{\sl AMM \bf 43} (1936), 610--617],
who discussed the properties of non-integer radices and remarked
in a footnote that negative radices would be feasible too. After
twenty more years the idea was rediscovered again, this time
by Z. \α{Pawlak} and A. \α{Wakulicz} [{\sl Bulletin de l'Academie Polonaise
des Sciences}, Classe III, {\bf 5} (1957), 233--236;
S\'erie des sciences techniques {\bf 7} (1959), 713--721], and
also by L. \α{Wadel} [{\sl IRE Transactions} {\bf EC-6} (1957), 123].
For further references see {\sl IEEE Transactions} {\bf EC-12}
(1963), 274--276; {\sl Computer Design \bf 6} (May 1967), 52--63.
There is evidence that the idea of negative bases occurred
independently to quite a few people. For example, D. E. \α{Knuth}
had discussed negative-base systems in 1955, together with a
further generalization to complex-valued bases, in a short paper
submitted to a ``science talent search'' contest for high-school
seniors.

The base $2i$ gives rise to a system called the ``\α{quater-imaginary}''
\inxf{complex radices}
number system (by analogy with ``quaternary''), which has the
unusual feature that {\sl every
complex number can be represented with the digits $0$, $1$, $2$,
and $3$ without a sign}.\xskip [See D. E. \α{Knuth}, {\sl CACM
\bf 3} (1960), 245--247.]\xskip For example,
$$\eqalign{(11210.31)↓{2i}⊗ \textstyle= 1 \cdot 16 + 1 \cdot (-8i) + 2 \cdot
(-4) + 1 \cdot (2i) + 3 \cdot (-{1\over 2}i) + 1(-{1\over 4})\cr
\noalign{\vskip 3pt}
⊗\textstyle= 7{3\over 4} - 7{1\over 2}i.\cr}$$
Here the number $(a↓{2n} \ldotsm a↓1a↓0.a↓{-1} \ldotsm
a↓{-2k})↓{2i}$ is equal to
$$(a↓{2n} \ldotsm a↓2a↓0.a↓{-2} \ldotsm a↓{-2k})↓{-4} + 2i(a↓{2n-1}
\ldotsm a↓3a↓1.a↓{-1} \ldotsm a↓{-2k+1})↓{-4},$$
so conversion to and from quater-imaginary notation
\inx{radix conversion}
reduces to conversion to and from negative quaternary representation
of the real and imaginary parts. The interesting property of
this system is that it allows multiplication and division of
complex numbers to be done in a fairly unified manner without
treating real and imaginary parts separately. For example, we
can multiply two numbers in this system much as we do with any
base, merely using a different ``carry'' rule: whenever a digit
exceeds 3 we subtract 4 and ``carry'' $-1$ two columns to the
left; when a digit is negative, we add 4 to it and ``carry''
$+1$ two columns to the left. A study of the following example
shows this peculiar carry rule at work:
$$\def\\{\hskip 5pt}
\teqalign{1\\2\\2\\3\\1⊗\qquad[9-10i]\cr
1\\2\\2\\3\\1⊗\qquad[9-10i]\cr
\noalign{\vskip -8.6pt}
\vbox{\hrule width 45pt}\cr
\noalign{\vskip-2pt}
1\\2\\2\\3\\1\cr
1\\0\\3\\2\\0\\2\\1\\3\\\\\cr
1\\3\\0\\2\\2\\\\\\\\\cr
1\\3\\0\\2\\2\\\\\\\\\\\\\cr
1\\2\\2\\3\\1\\\\\\\\\\\\\\\\\cr
\noalign{\vskip 3pt\hrule width 85pt\vskip 3pt}
0\\2\\1\\3\\3\\3\\1\\2\\1⊗\qquad[-19-180i]\cr}$$
A similar system that uses just the digits 0
and 1 may be based on $\sqrt2\,i$, but this
requires an infinite nonrepeating expansion for the simple number
``$i$'' itself. Vittorio \α{Gr\"unwald} proposed using the digits 0 and
$1/\sqrt2$ in odd-numbered positions, to avoid such a problem, but
this actually spoils the whole system [cf.\ {\sl Commentari dell' Ateneo di Brescia}
(1886), 43--54].

Another ``binary'' complex number system may be obtained by using
the base $i - 1$, as suggested by W. \α{Penney} [{\sl JACM \bf 12}
(1965), 247--248]:
$$\twoline{(\ldotsm a↓4a↓3a↓2a↓1a↓0.a↓{-1}\ldotsm)↓{i-1}}{3pt}{\textstyle
=\cdots-4a↓4+(2\<+\<2i)a↓3-2ia↓2+(i\<-\<1)a↓1+a↓0-{1\over2}(i\<+\<1)a↓{-1}
+\cdotss.}$$
In this system, only the digits 0 and 1
are needed. One way to demonstrate that every complex number has such
a representation is to consider the interesting set $S$ shown
in Fig.↔1; this set is, by definition, all points that can
be written as $\sum ↓{k≥1} a↓k(i - 1)↑{-k}$, for an infinite
sequence $a↓1$, $a↓2$, $a↓3$, $\ldots$ of zeros and ones. Figure↔1
shows that $S$ can be decomposed into 256 pieces congruent to
${1\over 16}S$; note that if the diagram of $S$ is rotated
counterclockwise by $135\deg$, we obtain two adjacent sets congruent
to $(1/\sqrt{2})\,S$ $\biglp$since $(i - 1)S = S ∪
(S + 1)\bigrp $. For details of a proof that $S$ contains all
complex numbers that are of sufficiently small magnitude, see
exercise↔18.

\topinsert{\vskip 122mm
\ctrline{\caption Fig.\ 1. The set $S$.\xskip (Illustration by P. M. \α{Farmwald},
\inx{twindragon}
R. W. \α{Gosper}, and R. E. \α{Maas}.)}}
%folio 249 galley 5 (C) Addison-Wesley 1978	*
\def\≡{\overline1}
\def\\{\hskip 5pt}
\yskip Perhaps the prettiest number system
\inxf{balanced ternary number system}
of all is the {\sl balanced ternary} notation, which consists
of base-3 representation using $-1$, 0, and $+1$ as ``\α{trits}'' (ternary digits)
instead of 0, 1, and 2. If we use the symbol $\≡$ to stand for
$-1$, we have the following examples of balanced ternary
numbers:\hfil\eject % almost mandatory page break (April 1980)
$$\vbox{\baselineskip13pt
\halign{\rt{$# $}⊗\lft{$# $}\qquad⊗\rt{$# $}⊗\lft{$\textstyle#$}\cr
\hbox{Balanc}⊗\hbox{ed ternary}⊗\hbox{Decim}⊗\hbox{al}\cr
\noalign{\vskip 2pt}
1\ 0\ \≡⊗⊗8\cr
1\ 1\ \≡\ 0⊗.\≡\ \≡⊗32⊗{5\over9}\cr
\≡\ \≡\ 1\ 0⊗.1\ 1⊗-32⊗{5\over9}\cr
\≡\ \≡\ 1\ 0⊗⊗-33\cr
0⊗.1\ 1\ 1\ 1\ 1\ldots⊗⊗{1\over2}\cr}}$$

One way to find the representation of a number in the balanced
ternary system is to start by representing it in ternary
notation; for example,
$$208.3 = (21201.022002200220\ldotsm)↓3.$$
(A very simple pencil-and-paper method for converting
\inx{radix conversion}
to ternary notation is given in exercise 4.4--12.)\xskip Now add the
infinite number $\ldotss 11111.11111\,\ldots$ in ternary notation;
we obtain, in the above example, the infinite number
$$(\ldotsm 11111210012.210121012101\ldotsm)↓3.$$
Finally, subtract $\ldotss 11111.11111\,\ldots$ by decrementing
each digit; we get
$$208.3 = (10\≡\≡01.10\≡010\≡010\≡0\ldotsm)↓3.\eqno(8)$$
This process may clearly be made rigorous if we
replace the artificial infinite number $\ldotss 11111.11111\,\ldots$
by a number with suitably many ones.

The balanced ternary number system has many pleasant
properties:

\yyskip\textindent{a)}\hang The negative of a number is obtained by interchanging
1 and $\≡$.

\yskip\textindent{b)}\hang The sign of a number is given by its most significant
nonzero ``trit,'' and in general we can compare any two numbers
by reading them from left to right and using lexicographic order,
as in the decimal system.

\yskip\textindent{c)}\hang The operation of rounding to the nearest integer is
identical to truncation (i.e., deleting everything to the right of the
radix point).

\yyskip\noindent \α{Addition} in the balanced ternary
system is quite simple, using the table
$$\def\\{\vbox{\hrule width 10pt}}\def\≡{$\overline1$}
\vbox{\halign to size{\hfill#\tabskip 0pt plus 3pt⊗\hfill#⊗\hfill#⊗\hfill
#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill
#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill
#⊗\hfill#⊗\hfill#⊗\hfill#\tabskip 0pt\cr
\≡⊗\≡⊗\≡⊗\≡⊗\≡⊗\≡⊗\≡⊗\≡⊗\≡⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗1⊗1⊗1⊗1⊗1⊗1⊗1⊗1⊗1\cr
\≡⊗\≡⊗\≡⊗0⊗0⊗0⊗1⊗1⊗1⊗\≡⊗\≡⊗\≡⊗0⊗0⊗0⊗1⊗1⊗1⊗\≡⊗\≡⊗\≡⊗0⊗0⊗0⊗1⊗1⊗1\cr
\≡⊗0⊗1⊗\≡⊗0⊗1⊗\≡⊗0⊗1⊗\≡⊗0⊗1⊗\≡⊗0⊗1⊗\≡⊗0⊗1⊗\≡⊗0⊗1⊗\≡⊗0⊗1⊗\≡⊗0⊗1\cr
\noalign{\vskip -8.6pt}
\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\⊗\\\cr
\noalign{\vskip -2pt}
\≡0⊗\≡1⊗\≡⊗\≡1⊗\≡⊗0⊗\≡⊗0⊗1⊗\≡1⊗\≡⊗0⊗\≡⊗0⊗1⊗0⊗1⊗1\≡⊗\≡⊗0⊗1⊗0⊗1⊗1\≡⊗1⊗1\≡⊗10\cr}}$$
(The three inputs to the addition are the digits
of the numbers to be added and the carry digits.)\xskip \α{Subtraction}
is negation followed by addition; and \α{multiplication} also reduces
to negation and addition, as in the following example:
$$\teqalign{1\\\≡\\0\\\≡⊗\qquad[17]\cr
1\\\≡\\0\\\≡⊗\qquad[17]\cr
\noalign{\vskip -8.6 pt}
\vbox{\hrule width 35pt}\cr
\noalign{\vskip -2pt}
\≡\\1\\0\\1\cr
\≡\\1\\0\\1\\0\\\\\cr
1\\\≡\\0\\\≡\\\\\\\\\\\\\cr
\noalign{\vskip 3pt \hrule width 65pt \vskip 1.5pt}
0\\1\\1\\\≡\\\≡\\0\\1⊗\qquad[289]\cr}$$

Representation of numbers in the balanced ternary system is
implicitly present in a famous mathematical puzzle, which is
commonly called ``\α{Bachet}'s problem of weights'' although it
was already stated by \α{Fibonacci} four centuries before Bachet
wrote his book.\xskip [See W. \α{Ahrens,} {\sl Mathematische Unterhaltungen
und Spiele \bf 1} (Leipzig: Teubner, 1910), Section 3.4.]\xskip
Positional number systems with negative digits have apparently
been known for more than 1000 years in India; see J. \α{Bharati},
\inx{Indian mathematics}
{\sl Vedic Mathematics} (Delhi: Motilal Banarsidass, 1965). They were
independently rediscovered by J. \α{Colson} [{\sl Philos.\ Trans.\ \bf 34} (1726),
161--173], and by Sir John \α{Leslie} [{\sl The Philosophy of
Arithmetic} (Edinburgh, 1817); see pp.\ 33--34, 54, 64--65, 117,
150]; and also by A. \α{Cauchy} [{\sl Comptes Rendus \bf 11}
(Paris: 1840), 789--798], who pointed out that negative digits
make it unnecessary for a person to memorize the multiplication
table past $5 \times 5$. The first true appearance of ``pure''
balanced ternary notation was in an article by L\'eon
\α{Lalanne} [{\sl Comptes Rendus \bf 11} (Paris: 1840), 903--905],
who was a designer of mechanical devices for arithmetic. The
system was mentioned only rarely for 100 years after Lalanne's
paper, until the development of the first electronic computers
at the Moore School of Electrical Engineering in 1945--1946;
at that time it was given serious consideration along with the
binary system as a possible replacement for the decimal system.
The complexity of arithmetic circuitry for balanced ternary
arithmetic is not much greater than it is for the binary system,
and a given number requires only $\ln 2/\ln 3 \approx 63\%$ as many
digit positions for its representation. Discussions of the balanced
ternary number system appear in {\sl AMM \bf 57} (1950), 90--93,
and in {\sl High-speed Computing Devices}, \α{Engineering Research
Associates} (McGraw-Hill, 1950), 287--289. The experimental Russian
computer \α{SETUN} was based on balanced ternary notation [see {\sl
CACM \bf 3} (1960), 149--150], and perhaps the symmetric properties
and simple arithmetic of this number system will prove to be
quite important some day---when the ``flip-flop'' is replaced
by a ``flip-flap-flop''.

\yskip Positional notation generalizes in another important way
to a {\sl mixed-radix} system. Given a sequence of numbers
\inxf{mixed-radix number system}
$\langle b↓n\rangle$ (where $n$ may be negative), we define
$$\eqalign{⊗\mskip-50mu\left[\vcenter{\halign{\rt{$#$}⊗\rt{$\,#$}⊗\rt{$\,#$}⊗\rt{$\,
#$}⊗\rt{$\,#$}⊗\rt{$\;#$}⊗\rt{$\;#\ldotsm$}\cr
\ldotsm,⊗a↓3,⊗a↓2,⊗a↓1,⊗a↓0;⊗a↓{-1},⊗a↓{-2},\cr
\ldotsm,⊗b↓3,⊗b↓2,⊗b↓1,⊗b↓0;⊗b↓{-1},⊗b↓{-2},\cr}}\right]\cr
\noalign{\vskip 3pt}
⊗\mskip-32mu= \cdots + a↓3b↓2b↓1b↓0 + a↓2b↓1b↓0 + a↓1b↓0
+ a↓0 + a↓{-1}/b↓{-1} + a↓{-2}/b↓{-1}b↓{-2} + \cdotss.\mskip-50mu\cr}\eqno(9)$$
In the simplest mixed-radix systems, we work
only with integers; we let $b↓0$, $b↓1$, $b↓2$,↔$\ldots$ be integers
greater than one, and deal only with numbers that have no radix
point, where $a↓n$ is required to lie in the range $0 ≤ a↓n
< b↓n$.

One of the most important mixed-radix systems is
the {\sl \α{factorial number system}}, where $b↓n = n + 2$. Using
this system, we can represent every positive integer uniquely
in the form
$$c↓n\,n! + c↓{n-1}\,(n - 1)! + \cdots + c↓2\,2! + c↓1,\eqno (10)$$
where $0 ≤ c↓k ≤ k$ for $1≤k≤n$, and $c↓n ≠ 0$.\xskip (See Algorithm
3.3.2P.)

Mixed-radix systems are familiar in everyday life, when we deal
with units of measure. For example, the quantity ``3 weeks,
\inxf{weights and measures}
2 days, 9 hours, 22 minutes, 57 seconds, and 492 milliseconds''
is equal to
$$\left[\vcenter{\halign{\rt{#}⊗\rt{ #}⊗\rt{ #}⊗\rt{ #}⊗\rt{ #}⊗\rt{ #}\cr
3,⊗2,⊗9,⊗22,⊗57;⊗492\cr ⊗7,⊗24,⊗60,⊗60;⊗1000\cr}}\right]\hbox{ seconds.}$$
The quantity ``10 pounds, 6 shillings, and thruppence
ha'penny'' was once equal to 
$[{10,\atop \null}\,{\hfill 6,\atop 20,}\,{\hfill 3;\atop
12;}\,{1\atop 2}]$ pence in British currency, before Great Britain
changed to a purely decimal monetary system.

It is possible to add and subtract mixed-radix numbers by using
a straightforward generalization of the usual addition and subtraction
algorithms, provided of course that the same mixed-radix system
is being used for both operands (see exercise 4.3.1--9). Similarly,
we can easily multiply or divide a mixed-radix number by small
integer constants, using simple extensions of the familiar pencil-and-paper
methods.

Mixed-radix systems were first discussed in full generality by Georg
\α{Cantor} [{\sl Zeitschrift f\"ur Math.\ und Physik \bf 14}
(1869), 121--128]. Exercises 26 and↔29 give further information about them.

\yskip Some questions concerning {\sl irrational} radices have been
investigated by W. \α{Parry,} {\sl Acta Mathematica}, Acad.\ Sci.\
Hung., {\bf 11} (1960), 401--416.

Besides the systems described in this section, several
other ways to represent numbers are mentioned elsewhere
in this series of books: the \α{binomial number system} (exercise 1.2.6--56);
the \α{Fibonacci number system} (exercises 1.2.8--34, 5.4.2--10); the \α{phi number
system} (exercise 1.2.8--35); modular representations (Section
4.3.2); \α{Gray code} (Section 7.2.1); and \α{roman numerals} (Section↔9.1).

\exbegin{EXERCISES}

\exno 1. [15] Express
$-10$, $-9$, $\ldotss$, 9, 10 in the number system whose base is $-2$.

\trexno 2. [24] Consider the following four number systems:\xskip (a)
\β{binary} (\β{signed magnitude});\xskip (b) \β{negabinary} (radix $-2$);\xskip (c)
\β{balanced ternary}; and\xskip (d) radix $b = {1\over 10}$. Use each
of these four number systems to express each of the following three
numbers:\xskip (i) $-49$;\xskip (ii) $-3{1\over 7}$ (show the repeating
cycle);\xskip(iii) $π$ (to a few significant figures).

\exno 3. [20] Express $-49 + i$ in the \β{quater-imaginary}
\inxf{radix, complex}
system.

\exno 4. [15] Assume that we have a \α{\MIX}\ program in which location
\.A contains a number for which the \α{radix point} lies between bytes
3 and↔4, while location \.B contains a number whose radix point
lies between bytes 2 and↔3.\xskip (The leftmost byte is number↔1).\xskip
Where will the radix point be, in registers A and↔X, after the
following instructions?
$$\vbox{\halign{#⊗\qquad\tt#⊗\quad\tt#\hfill\hskip 25mm⊗#⊗\qquad\tt#\hfill
⊗\quad\tt#\hfill\cr
a)⊗LDA⊗A⊗b)⊗LDA⊗A\cr
⊗MUL⊗B\quad\blackslug⊗⊗SRAX⊗5\cr
⊗⊗⊗⊗DIV⊗B\quad\blackslug\qquad\qquad\cr}}$$

\exno 5. [00] Explain why a negative integer
in \β{nines' complement} notation has a representation in \β{ten's
complement} notation that is always one greater, if the representations
\inxf{complement notations}
are regarded as positive.
%folio 254 galley 6 (C) Addison-Wesley 1978	*
\exno 6. [16] What are the
largest and smallest $p$-bit integers that can be represented
in (a) signed-magnitude binary notation (including one
bit for the sign),\xskip (b) two's com\-plement
notation,\xskip (c) ones' complement notation?

\exno 7. [M20] The text defines ten's complement notation only
for integers represented in a single computer word. Is there
a way to define a ten's complement notation {\sl for all real
numbers}, having ``infinite precision,'' analogous to the text's
definition? Is there a similar way to define a nines' complement
notation for all real numbers?

\exno 8. [M10] Prove Eq.\ (5).

\trexno 9. [15] Change the following {\sl \α{octal}\/} numbers to {\sl
\α{hexadecimal}} notation, using the hexadecimal digits \.0, \.1, $\ldotss$,
\.F: {\it 12\/}; {\it 5655\/}; {\it 2550276\/}; {\it 76545336\/};
{\it 3726755.}

\exno 10. [M22] Generalize Eq.\ (5) to \β{mixed-radix notation}.

\exno 11. [22] Design an algorithm that uses the $-2$ number system
to compute the sum of
$(a↓n\ldotsm a↓1a↓0)↓{-2}$ and $(b↓n \ldotsm b↓1b↓0)↓{-2}$,
obtaining the answer $(c↓{n+2} \ldotsm c↓1c↓0)↓{-2}$.

\exno 12. [23] Specify algorithms that convert (a) the binary signed
\inx{radix conversion}
magnitude number $\pm (a↓n \ldotsm a↓0)↓2$ to its negabinary
form $(b↓{n+1} \ldotsm b↓0)↓{-2}$; and\xskip (b) the negabinary
number $(b↓{n+1} \ldotsm b↓0)↓{-2}$ to its signed magnitude form
$\pm (a↓{n+1} \ldotsm a↓0)↓2$.

\trexno 13. [M21] In the \β{decimal system} there are some numbers
with two infinite decimal expansions; e.g., $2.3599999\,\ldots
= 2.3600000\,\ldotss\,$. Does the {\sl negadecimal} (base $-10$)
system have unique expansions, or are there real numbers with
two different infinite expansions in this base also?

\exno 14. [14] Multiply $(11321)↓{2i}$ by itself in the quater-imaginary
system using the method illustrated in the text.

\exno 15. [M24] What are the sets $$S = \left.\left\{\,
\chop to 9pt{\sum↓{k≥1}a↓kb↑{-k}
}\;\right|\; a↓k \hbox{ an allowable digit}\,\right\},$$ analogous to Fig.↔1,
\inx{negadecimal}
for the negative decimal and for the quater-imaginary number systems?

\exno 16. [M24] Design an algorithm to add 1 to $(a↓n \ldotsm
a↓1a↓0)↓{i-1}$ in the $i - 1$ number system.

\exno 17. [M30] It may seem peculiar that $i - 1$
has been suggested as a number-system base, instead of the similar
but intuitively simpler number $i + 1$. Can every complex number $a + bi$,
where $a$ and $b$ are integers, be represented in a positional
number system to base $i + 1$, using only the digits 0 and 1?

\exno 18. [\HM32] Show that the set $S$ of Fig.↔1 is a closed
set that contains a neighborhood of the origin.\xskip (Consequently,
every complex number has a ``binary'' representation to base
$i - 1$.)

\trexno 19. [23] (David W. \β{Matula}.)\xskip Let $D$ be a set of $b$ integers,
containing exactly one solution to the congruence $x ≡ j \modulo
b$ for $0 ≤ j < b$. Prove that all integers $m$ (positive,
negative, or zero) can be represented in the form $m = (a↓n
\ldotsm a↓0)↓b$, where all the $a↓j$ are in $D$, if and only
if all integers in the range $l ≤ m ≤ u$ can be so represented,
where $l = -\max\leftset a \relv a \in D\rightset/(b - 1)$, $u = -\min
\leftset a \relv a\in D\rightset
/(b - 1)$. For example, $D = \{-1, 0, \ldotss , b
- 2\}$ satisfies the conditions for all $b ≥ 3$.\xskip [{\sl Hint:}
Design an algorithm that constructs a suitable representation.]

\exno 20. [\HM28] (David W. Matula.)\xskip Consider a decimal number
system that uses the digits $D = \{-1, 0, 8, 17, 26, 35, 44,
53, 62, 71\}$ instead of $\{0, 1, \ldotss , 9\}$. The result
of exercise↔19 implies (as in exercise↔18) that all real numbers
have an infinite decimal expansion using digits from $D$.

In the usual decimal system, some numbers have
two representations (cf.\ exercise↔13).\xskip (a) Find a real number
that has {\sl more} than two $D$-decimal representations.\xskip (b)
Show that no real number has infinitely many $D$-decimal representations.\xskip
(c) Show that uncountably many numbers have two or more $D$-decimal
representations.

\trexno 21. [M22] (C. E. \α{Shannon}.)\xskip Can every
real number (positive, negative, or zero) be expressed in a
``\α{balanced-decimal}'' system, i.e., in the form $\sum ↓{k≤n}
a↓k10↑k$, for some integer $n$ and some sequence $a↓n$, $a↓{n-1}$,
$a↓{n-2}$, $\ldotss $, where each $a↓k$ is one of the ten numbers
$\{-4{1\over 2}, -3{1\over 2}, -2{1\over 2}, -1{1\over
2}, -{1\over 2}, {1\over 2}, 1{1\over 2}, 2{1\over 2},
3{1\over 2}, 4{1\over 2}\}$?\xskip (Note that zero is not one of
the allowed digits, but we implicitly assume that $a↓{n+1}$,
$a↓{n+2}$, $\ldots$ are zero.)\xskip Find all representations of zero
in this number system, and find all representations of unity.

\exno 22. [\HM25] Let $α = -\sum ↓{m≥1} 10↑{-m↑2}$.
Given $ε > 0$ and any real number $x$, prove that there is
a ``decimal'' representation such that $0 < \left|x - \sum ↓{0≤k≤n}
a↓k10↑k\right| < ε$, where each $a↓k$ is allowed to be only one
of the three values 0, 1, or $α$.\xskip (Note that no negative powers
of 10 are used in this representation!)

\exno 23. [\HM30] Let $D$ be a set of $b$ real numbers such that
every positive real number has a representation $\sum ↓{k≤n}
a↓kb↑k$ with all $a↓k \in D$. Exercise↔20 shows that
there may be many numbers without {\sl unique} representations;
but prove that the set $T$ of all such numbers has measure zero.

\exno 24. [M35] Find infinitely many different sets $D$ of ten
nonnegative integers satisfying the following three conditions:\xskip
(i) $\gcd(D) = 1$;\xskip (ii) $0 \in D$;\xskip (iii) every positive real
number can be represented in the form $\sum ↓{k≤n} a↓k10↑k$
with all $a↓k \in D$.

\exno 25. [M25] (S. A. \α{Cook}.)\xskip Let $b$, $u$, and $v$ be positive
integers, where $b ≥ 2$ and $0 < v < b↑m$. Show that the base
$b$ representation of $u/v$ does not contain a run of $m$ consecutive
\inx{rational number, positional representation of}
digits equal to $b - 1$, anywhere to the right of the radix point.\xskip (By
convention, no runs of infinitely many $(b - 1)$'s are permitted
in the standard base $b$ representation.)

\trexno 26. [\HM30] (N. S. \α{Mendelsohn}.)\xskip Let $\langle β↓n\rangle$
be a sequence of real numbers defined for all integers $n$, $-∞
< n < ∞$, such that
$$β↓n < β↓{n+1};\qquad\lim↓{n→∞}β↓n = ∞;\qquad\lim↓{n→-∞} β↓n = 0.$$
Let $\langle c↓n\rangle$ be an arbitrary sequence
of positive integers that is defined for all integers↔$n$, $-∞ < n <
∞$. Let us say that a number $x$ has a ``generalized representation''
if there is an integer $n$ and an infinite sequence of integers $a↓n$,
$a↓{n-1}$, $a↓{n-2}$, $\ldots$ such that $x = \sum ↓{k≤n} a↓kβ↓k$,
where $a↓n ≠ 0$, $0 ≤ a↓k ≤ c↓k$, and $a↓k < c↓k$ for infinitely
many $k$.

Show that every positive real number $x$ has exactly
one generalized representation if and only if $β↓{n+1} = \sum
↓{k≤n} c↓kβ↓k$ for all $n$.\xskip (Consequently, the mixed-radix
systems with integer bases have this property; and mixed-radix
systems with $β↓1 = (c↓0 + 1)β↓0$, $β↓2 = (c↓1 + 1)(c↓0
+ 1)β↓0$, $\ldotss$, $β↓{-1} = β↓0/(c↓{-1} + 1)$, $\ldots$ are the most
general number systems of this type.)

\exno 27. [M21] Show that every nonzero integer has a unique
``\α{reversing binary representa\-tion}'' $$2↑{e↓0}-2↑{e↓1}+\cdots+(-1)↑t2↑{e↓t},$$
where $e↓0 < e↓1 < \cdots < e↓t$.

\trexno 28. [M24] Show that every nonzero complex number of the
form $a + bi$ where $a$ and $b$ are integers has a unique ``\α{revolving
binary representation}''
$$(1 + i)↑{e↓0} + i(1 + i)↑{e↓1} - (1
+ i)↑{e↓2} - i(1 + i)↑{e↓3} + \cdots + i↑t(1 + i)↑{e↓t},$$
where $e↓0 < e↓1 < \cdots < e↓t$.\xskip (Cf.\ exercise↔27.)

\exno 29. [M35] (N. G. \β{de Bruijn}.)\xskip Let $S↓0$, $S↓1$, $S↓2$, $\ldots$
be sets of nonnegative integers; we will say that the collection
$\{S↓0, S↓1, S↓2, \ldotss\}$ has Property↔B if every nonnegative in\-te\-ger↔$n$
can be written in the form
$$n = s↓0 + s↓1 + s↓2 + \cdotss,\qquad s↓j \in S↓j,$$
in exactly one way.\xskip (Property↔B implies that $0
\in S↓j$ for all $j$, since $n = 0$ can only be represented
as $0 + 0 + 0 + \cdotss$.)\xskip Any mixed-radix number system with
radices $b↓0$, $b↓1$,↔$b↓2$, $\ldots$ provides an example of a collection
of sets satisfying
Property↔B, if we let $S↓j = \{0, B↓j, \ldotss , (b↓j - 1)B↓j\}$,
where $B↓j = b↓0b↓1 \ldotsm b↓{j-1}$; here the representation
of $n = s↓0 + s↓1 + s↓2 + \cdots$ corresponds in an obvious manner
to its mixed-radix rep\-re\-senta\-tion↔(9). Furthermore, if the collection $\{S↓0,
S↓1, S↓2, \ldotss\}$ has Property↔B, and if $A↓0$, $A↓1$, $A↓2$,↔$\ldots$
is any partition of the nonnegative integers (so that we have $A↓0
∪ A↓1 ∪ A↓2 ∪ \cdots = \{0, 1, 2, \ldotss\}$ and $A↓i ∩ A↓j =
\emptyset$ for $i ≠ j$; some $A↓j$'s may be empty), then the ``collapsed''
collection $\{T↓0, T↓1, T↓2, \ldotss\}$ also has Property↔B, where
$T↓j$ is the set of all sums $\sum ↓{i\in A↓j} s↓i$ taken
over all possible choices of $s↓i \in S↓i$.

Prove that {\sl any} collection $\{T↓0, T↓1, T↓2, \ldotss\}$
that satisfies Property↔B may be obtained by collapsing
some collection $\{S↓0, S↓1, S↓2, \ldotss\}$ that corresponds to a
mixed-radix number system.

\exno 30. [M39] (N. G. de Bruijn.)\xskip The radix-$(-2)$ number system
shows us that every integer (positive, negative, or zero) has
a unique representation of the form
$$(-2)↑{e↓1}+ (-2)↑{e↓2} + \cdots + (-2)↑{e↓t},
\qquad e↓1 > e↓2 > \cdots > e↓t ≥ 0,\qquad t ≥ 0.$$
The purpose of this exercise is to explore generalizations
of this phenomenon.

\yskip\textindent{a)}\hang Let $b↓0$, $b↓1$, $b↓2$, $\ldots$ be a sequence of
integers such that every integer↔$n$ has a unique representation
of the form
$$n = b↓{e↓1} + b↓{e↓2}+ \cdots + b↓{e↓t}
,\qquad e↓1 > e↓2 > \cdots > e↓t ≥ 0,\qquad t ≥ 0.$$
(Such a sequence $\langle b↓n\rangle$ is
called a ``\α{binary basis}.'') Show that there is an index $j$
such that $b↓j$ is odd, but $b↓k$ is even for all $k ≠ j$.

\yskip\textindent{b)}\hang Prove that a binary basis $\langle b↓n\rangle$
can always be rearranged into the form $d↓0$, $2d↓1$, $4d↓2$, $\ldots
 = \langle 2↑nd↓n\rangle $, where each $d↓k$ is odd.

\yskip\textindent{c)}\hang If each of $d↓0$, $d↓1$, $d↓2$, $\ldots$ in (b) is
$\pm 1$, prove that $\langle b↓n\rangle$ is a binary basis if and only
if there are infinitely many $+1$'s and infinitely many $-1$'s.

\yskip\textindent{d)}\hang Prove that $7$, $-13 \cdot 2$, $7 \cdot 2↑2$, $-13
\cdot 2↑3$, $\ldotss$, $7 \cdot 2↑{2k}$, $-13 \cdot 2↑{2k+1}$, $\ldots$
is a binary basis, and find the representation of $n = 1$.

\trexno 31. [M35] A
generalization of two's complement arithmetic, called ``\α{2-adic
numbers},'' was invented about 1900 by K. Hensel.\xskip (In fact he
treated {\sl \α{$p$-adic numbers}}, for any prime $p$.)\xskip A 2-adic number
may be regarded as a binary number
$$u = (\ldotsm u↓3u↓2u↓1u↓0.u↓{-1} \ldotsm u↓{-n})↓2,$$
whose representation extends infinitely far to
the left, but only finitely many places to the right, of the
binary point. Addition, subtraction, and multiplication of 2-adic
numbers are done according to the ordinary procedures of arithmetic,
which can in principle be extended indefinitely to the left.
For example,
$$\vbox{\ctrline{$
\eqalign{7⊗= (\ldotsm 000000000000111)↓2\cr
\noalign{\vskip 2pt}
-7⊗=(\ldotsm111111111111001)↓2\cr
\noalign{\vskip 2pt}
\textstyle{7\over4}⊗=(\ldotsm000000000000001.11)↓2\cr}\qquad\qquad
\eqalign{\textstyle{1\over7}⊗=(\ldotsm110110110110111)↓2\cr
\noalign{\vskip 2pt}
\textstyle-{1\over7}⊗=(\ldotsm001001001001001)↓2\cr
\noalign{\vskip 2pt}
\textstyle{1\over10}⊗=(\ldotsm110011001100110.1)↓2\cr}$}
\vskip 5pt
\ctrline{$\sqrt{-7}=(\ldotsm100000010110101)↓2$\quad or \quad$(\ldotsm
011111101001011)↓2$.}}$$
%folio 259 galley 7a (C) Addison-Wesley 1978	*
Here 7 appears as the ordinary binary integer
seven, while $-7$ is its two's complement (extending infinitely
to the left); it is easy to verify that the ordinary procedure
for addition of binary numbers will give $-7 + 7 = (\ldotsm 00000)↓2
= 0$, when the procedure is continued indefinitely. The values
of ${1\over 7}$ and $-{1\over 7}$ are the unique 2-adic numbers
that, when formally multiplied by 7, give 1 and $-1$, respectively.
The values of ${7\over 4}$ and ${1\over 10}$ are examples of 2-adic
numbers that are not 2-adic ``integers,'' since they have nonzero
bits to the right of the binary point. The two values of
$\sqrt{-7}$, which are negatives of each other, are the
only 2-adic numbers that, when formally squared, yield the value
$(\ldotsm 111111111111001)↓2$.

\yskip\textindent{a)}\hang Prove that any 2-adic number $u$ can be divided
by any nonzero 2-adic number $v$ to obtain a unique 2-adic number
$w$ satisfying $u = vw$.\xskip (Hence the set of 2-adic numbers forms
a ``\α{field}''; cf.\ Section 4.6.1.)

\yskip\textindent{b)}\hang Prove that the 2-adic representation of the
rational number $-1/(2n + 1)$ may be obtained as follows, when
$n$ is a positive integer: First find the ordinary binary expansion
of $+1/(2n + 1)$, which has the periodic form $(0.ααα\ldotsm)↓2$
for some string $α$ of 0's and 1's. Then $-1/(2n + 1)$ is the
2-adic number $(\ldotsmααα)↓2$.

\yskip\textindent{c)}\hang Prove that the representation of a 2-adic number $u$
is periodic (that is, $u↓{N+λ} = u↓N$ for all large $N$, for
some $λ ≥ 1$) if and only if $u$ is rational (that is, $u =
m/n$, for some integers $m$ and $n$).

\yskip\textindent{d)}\hang Prove that, when $n$ is an integer,
\inx{square root}
$\sqrt{n}$ is a 2-adic number if and only if it sat\-is\-fies $n \mod
2↑{2k+3} = 2↑{2k}$ for some nonnegative integer↔$k$.\xskip (Thus,
the possibilities are either $n \mod 8 = 1$, or $n \mod 32 = 4$, etc.)

\exno 32. [M40] (I. Z. \α{Ruzsa}.)\xskip Prove that there are
infinitely many integers whose
ternary representation uses only 0's and 1's and whose quinary
\inx{ternary}
\inx{quinary}
representation uses only 0's, 1's, and↔2's.

\exno 33. [M40] (D. A. \α{Klarner}.)\xskip Let $D$ be any set of integers, let
$b$ be any positive integer, and let $k↓n$ be the number of distinct integers that
can be written as $n$-digit numbers $(a↓{n-1}\ldotsm a↓1a↓0)↓b$ to base $b$ with
digits $a↓i$ in↔$D$. Prove that the sequence $\langle k↓n\rangle$ satisfies a
linear recurrence relation, and explain how to compute the generating function
$\sum↓n k↓nz↑n$. Illustrate your algorithm in the case $b=3$ and $D=\{-1,0,3\}$.
\vfill\eject